package com.sfx.算法专题.前缀和.A总结题型;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: sfx
 * Date: 2023-08-03
 * Time: 21:28
 */
public class A总结题型 {
    /**
     *  一维前缀和模板总结 :
     *  前缀和可以快速求出数组中某一个连续区间的和
     *    1): 预处理出来一个前缀和数组
     *        dp[i]表示[1,i]区间内所有元素的和
     *        dp[i] = dp[i-1] + arr[i]
     *    2): 使用前缀和数组,快速求出某段连续区间的和
     *       计算[l...r]区间的和 = dp[r] - dp[l-1]
     *  前缀和细节问题 :
     *      1): 为什么数组下标从1开始计数 ?
     *          如果从0开始也可以,就是要处理一些边界的问题
     *          比如要[0,2]区间 dp[2] - dp[-1] ,这样还要处理边界的问题非常麻烦
     * 时间复杂度 遍历数组一遍 q次询问 ---> O(N*q)
__________________________________________________________________________________________________________
     *   二维前缀和模板总结 :
     *   1): 预处理出一个前缀和矩阵
     *   dp[i][j] 表示 从[1,1] ~ [i,j]之间的区域和
     *                         j
     *    _______________________
     *   |                |     |
     *   |        a       |  b  |
     *   |                |     |
     *   |________________|_____|
     * i |________c_______|____d|
     *   dp[i][j] =  a + b + c + d
     *   dp[i][j] =  a+b       +    a+c     +    d      -      a
     *   dp[i][j] = dp[i-1][j] + dp[i][j-1] + arr[i][j] - dp[i-1][j-1]
     *   2): 使用前缀和矩阵
     *   我们如果要求某个区间内的前缀和呢 ?
     *   [x1~y1] ~ [x2~y2]-->计算d区域的区间和
     *                     y1     y2
     *    __________________________
     *   |                |        |
     *   |        a       |  b     |
     *   |                |        |
     *   |________________|________|
     * x1|                |        |
     *   |        c       |   d    |
     * x2|________________|________|
     *   dp[[x1~y1] ~ [x2~y2]] = a + b + c + d -       (a+b)    -    (a+c)     +       a
     *                         = dp[x2][y2]    -   dp[x1-1][y2] - dp[x2][y1-1] +  dp[x1-1][y1-1];
     *  = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];
     *  二维前缀和 时间复杂度 :
     *  遍历二维数组 O(N*M*q) q次询问
     */
}